{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Deepest Leaves Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: deepestLeavesSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #层数最深叶子节点的和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树的根节点 <code>root</code> ，请你返回 <strong>层数最深的叶子节点的和</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/12/28/1483_ex1.png\" style=\"height: 265px; width: 273px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4,5,null,6,7,null,null,null,null,8]\n",
    "<strong>输出：</strong>15\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]\n",
    "<strong>输出：</strong>19\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[1, 10<sup>4</sup>]</code> 之间。</li>\n",
    "\t<li><code>1 <= Node.val <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [deepest-leaves-sum](https://leetcode.cn/problems/deepest-leaves-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [deepest-leaves-sum](https://leetcode.cn/problems/deepest-leaves-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,null,6,7,null,null,null,null,8]', '[6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDeepestLeavesSum(\n",
    "        self, node: TreeNode, depth: int, max_depth: List[int], max_depth_sum: [int],\n",
    "    ) -> None:\n",
    "        if node is None:\n",
    "            return\n",
    "        \n",
    "        if node.left is None and node.right is None:\n",
    "            if depth > max_depth[0]:\n",
    "                max_depth[0] = depth\n",
    "                max_depth_sum[0] = node.val\n",
    "            elif depth == max_depth[0]:\n",
    "                max_depth_sum[0] += node.val\n",
    "            \n",
    "        self.findDeepestLeavesSum(node.left, depth + 1, max_depth, max_depth_sum)\n",
    "        self.findDeepestLeavesSum(node.right, depth + 1, max_depth, max_depth_sum)\n",
    "\n",
    "\n",
    "    def deepestLeavesSum(self, root: TreeNode) -> int:\n",
    "        max_depth_sum: List[int] = [0]\n",
    "        self.findDeepestLeavesSum(root, 0, [0], max_depth_sum)\n",
    "        return max_depth_sum[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root):\n",
    "        dep = 0\n",
    "        sum = dict()\n",
    "        stack = list()\n",
    "        stack.append(root)\n",
    "        while stack:\n",
    "            node = stack[-1]\n",
    "            if dep not in sum:\n",
    "                sum[dep] = node.val\n",
    "            else:\n",
    "                sum[dep] += node.val\n",
    "            if node.left:\n",
    "                dep += 1\n",
    "                stack.append(node.left)\n",
    "                node.left = None\n",
    "                continue\n",
    "            elif node.right:\n",
    "                dep += 1\n",
    "                stack.append(node.right)\n",
    "                node.right = None\n",
    "                continue\n",
    "            else:\n",
    "                dep -= 1\n",
    "                stack.pop()\n",
    "        return sum[max(sum)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: TreeNode) -> int:\n",
    "        result = []\n",
    "\n",
    "        def helper(node, level):\n",
    "            if node == None:\n",
    "                return\n",
    "            if len(result) > level:\n",
    "                result[level].append(node.val)\n",
    "            else:\n",
    "                result.append([node.val])\n",
    "\n",
    "            helper(node.left, level + 1)\n",
    "            helper(node.right, level + 1)\n",
    "\n",
    "        helper(root, 0)\n",
    "        return sum(result[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: TreeNode) -> int:\n",
    "        result = []\n",
    "\n",
    "        def helper(node, level):\n",
    "            if node == None:\n",
    "                return\n",
    "            if len(result) > level:\n",
    "                result[level].append(node.val)\n",
    "            else:\n",
    "                result.append([node.val])\n",
    "\n",
    "            helper(node.left, level + 1)\n",
    "            helper(node.right, level + 1)\n",
    "\n",
    "        helper(root, 0)\n",
    "        \n",
    "        return sum(result[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: TreeNode) -> int:\n",
    "        if root==None:return None\n",
    "        stack=[root]\n",
    "        while(stack!=[]):\n",
    "            re=[]\n",
    "            for i in range(len(stack)):\n",
    "                if stack[i].left!=None:\n",
    "                    re.append(stack[i].left)\n",
    "                if stack[i].right!=None:\n",
    "                    re.append(stack[i].right)\n",
    "            if re==[]:\n",
    "                s=0\n",
    "                for i in range(len(stack)):\n",
    "                   s+=stack[i].val\n",
    "                return s \n",
    "            stack=re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: TreeNode) -> int:\n",
    "\n",
    "        leaves = defaultdict(list)\n",
    "\n",
    "        def search(node, level):\n",
    "            nonlocal leaves\n",
    "\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            if node.left is None and node.right is None:\n",
    "                leaves[level].append(node.val)\n",
    "\n",
    "            search(node.left, level + 1)\n",
    "            search(node.right, level + 1)\n",
    "\n",
    "        search(root, 1)\n",
    "        \n",
    "        max_level = max(leaves.keys())\n",
    "        return sum(leaves[max_level])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.maxdep = -1\n",
    "        self.total = 0\n",
    "\n",
    "    def deepestLeavesSum(self, root: TreeNode) -> int:\n",
    "\n",
    "        def dfs(node, dep):\n",
    "            if not node:\n",
    "                return\n",
    "            if dep > self.maxdep:\n",
    "                self.maxdep = dep\n",
    "                self.total = node.val\n",
    "            elif dep == self.maxdep:\n",
    "                self.total += node.val\n",
    "            dfs(node.left, dep+1)\n",
    "            dfs(node.right,dep+1)\n",
    "        dfs(root, 0)\n",
    "        return self.total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: TreeNode) -> int:\n",
    "        from collections import deque\n",
    "        queue = deque()\n",
    "        queue.append((root, 0))\n",
    "        max_depth, total = -1, 0\n",
    "        while queue:\n",
    "            node, depth = queue.popleft()\n",
    "            if depth == max_depth:\n",
    "                total += node.val\n",
    "            elif depth > max_depth:\n",
    "                max_depth, total = depth, node.val\n",
    "            if node.left:\n",
    "                queue.append((node.left, depth + 1))\n",
    "            if node.right:\n",
    "                queue.append((node.right, depth + 1))\n",
    "        \n",
    "        return total\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def deepestLeavesSum(self, root: TreeNode) -> int:\n",
    "#         q = collections.deque([(root, 0)])\n",
    "#         maxdep, total = -1, 0\n",
    "#         while len(q) > 0:\n",
    "#             node, dep = q.pop()\n",
    "#             if dep > maxdep:\n",
    "#                 maxdep, total = dep, node.val\n",
    "#             elif dep == maxdep:\n",
    "#                 total += node.val\n",
    "#             if node.left:\n",
    "#                 q.append((node.left, dep + 1))\n",
    "#             if node.right:\n",
    "#                 q.append((node.right, dep + 1))\n",
    "#         return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:\n",
    "        stack=[];dic={};level=0\n",
    "        unit=root;stack.append(root)\n",
    "        level_max=0\n",
    "\n",
    "        while(True):\n",
    "            if(unit.left!=None):\n",
    "                stack.append(unit);unit=unit.left\n",
    "                level+=1;stack[-1].left=None\n",
    "            elif(unit.right!=None):\n",
    "                stack.append(unit);unit=unit.right\n",
    "                level+=1;stack[-1].right=None\n",
    "            else:\n",
    "                if(level>=level_max):\n",
    "                    level_max=level\n",
    "                    if(level not in dic.keys()):\n",
    "                        dic[level]=[unit.val]\n",
    "                    else:\n",
    "                        dic[level].append(unit.val)\n",
    "                if(stack!=[]):\n",
    "                    unit=stack.pop();level-=1\n",
    "                else:\n",
    "                    break\n",
    "        re=dic[max(dic.keys())]\n",
    "        return sum(re)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.LeavesTotal = 0\n",
    "        self.Level = -1\n",
    "\n",
    "    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.DFS(root, 0)\n",
    "    \n",
    "    def DFS(self, root, level):\n",
    "        # base case\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        root.left = self.DFS(root.left, level + 1)\n",
    "        root.right = self.DFS(root.right, level + 1)\n",
    "\n",
    "        if level > self.Level:\n",
    "            self.Level = level\n",
    "            self.LeavesTotal = root.val\n",
    "        \n",
    "        elif level == self.Level:\n",
    "            self.LeavesTotal += root.val\n",
    "\n",
    "        return self.LeavesTotal\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def deepestLeavesSum(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return\n",
    "        queue = collections.deque([(root, 0)])\n",
    "        total, max_depth = 0, -1\n",
    "        while queue:\n",
    "            node, depth = queue.popleft()\n",
    "            if depth > max_depth:\n",
    "                max_depth, total = depth, node.val\n",
    "            elif depth == max_depth:\n",
    "                total += node.val\n",
    "            if node.left:\n",
    "                queue.append((node.left, depth + 1))\n",
    "            if node.right:\n",
    "                queue.append((node.right, depth + 1))\n",
    "        return total\n",
    "\n",
    "\n",
    "\n",
    "        helper(root, 0)\n",
    "        return self.total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        que = collections.deque([root])\n",
    "        while que:\n",
    "            ans = 0\n",
    "            for _ in range(0, len(que)):\n",
    "                node = que.popleft()\n",
    "                ans += node.val\n",
    "                if node.left:\n",
    "                    que.append(node.left)\n",
    "                if node.right:\n",
    "                    que.append(node.right)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:\n",
    "        res,queue=[],[root]\n",
    "        while queue:\n",
    "            res.append([node.val for node in queue])\n",
    "            l1=[]\n",
    "            for node in queue:\n",
    "                if node.left:\n",
    "                    l1.append(node.left)\n",
    "                if node.right:\n",
    "                    l1.append(node.right)\n",
    "            queue=l1\n",
    "        return sum(res[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        q = []\n",
    "        last_q = []\n",
    "        tmp_q = []\n",
    "        q.append(root)\n",
    "        while 1:\n",
    "            tmp_q = [v.val for v in q]\n",
    "            while q:\n",
    "                x = q.pop()\n",
    "                if x.left != None:\n",
    "                    last_q.append(x.left)\n",
    "                if x.right != None:\n",
    "                    last_q.append(x.right)\n",
    "            if len(last_q) == 0:\n",
    "                break\n",
    "            q = last_q\n",
    "            last_q = []\n",
    "            #print(tmp_q)\n",
    "\n",
    "        return sum(tmp_q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:\n",
    "        from collections import deque\n",
    "        next_level = deque([root,])\n",
    "        \n",
    "        while next_level:\n",
    "            curr_level = next_level\n",
    "            next_level = deque()\n",
    "\n",
    "            for node in curr_level:\n",
    "                # add child nodes of the current level\n",
    "                # in the queue for the next level\n",
    "                if node.left:\n",
    "                    next_level.append(node.left)\n",
    "                if node.right:\n",
    "                    next_level.append(node.right)\n",
    "\n",
    "        # print([node.val for node in curr_level])\n",
    "        return sum([node.val for node in curr_level])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        res = 1\n",
    "        queue = [root]\n",
    "\n",
    "        while queue:\n",
    "            tmp = []\n",
    "\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                tmp.append(node.val)\n",
    "\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            \n",
    "            res = sum(tmp)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        cur = []\n",
    "        q = []\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            cur = []\n",
    "            for i in range(l):\n",
    "                n = q.pop(0)\n",
    "                cur.append(n.val)\n",
    "                if n.left:\n",
    "                    q.append(n.left)\n",
    "                if n.right:\n",
    "                    q.append(n.right)\n",
    "        return sum(cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:\n",
    "        maxLevel,ans=-1,0\n",
    "        def dfs(node:Optional[TreeNode],level:int)->None:\n",
    "            if node is None:\n",
    "                return\n",
    "            nonlocal maxLevel,ans\n",
    "            if level>maxLevel:\n",
    "                maxLevel,ans=level,node.val\n",
    "            elif level==maxLevel:\n",
    "                ans+=node.val\n",
    "            dfs(node.left,level+1)\n",
    "            dfs(node.right,level+1)\n",
    "        dfs(root,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:\n",
    "        def travel(node,d,level):\n",
    "            if level in d:\n",
    "                d[level]+=node.val\n",
    "            else:\n",
    "                d[level]=node.val\n",
    "            if node.right:\n",
    "                d=travel(node.right,d,level+1)\n",
    "            if node.left:\n",
    "                d=travel(node.left,d,level+1)\n",
    "            return d\n",
    "        d=travel(root,{},0)\n",
    "        print(d)\n",
    "        return d[max(d)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            nxt = []\n",
    "            for node in queue:\n",
    "                if node.left: nxt.append(node.left)\n",
    "                if node.right: nxt.append(node.right)\n",
    "            if len(nxt) == 0: break\n",
    "            queue = nxt\n",
    "            \n",
    "        return sum([node.val for node in queue])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        qu = [root]\n",
    "        while qu:\n",
    "            ans = 0\n",
    "            size = len(qu)\n",
    "            for _ in range(size):\n",
    "                x = qu[0]\n",
    "                if x.left:\n",
    "                    qu.append(x.left)\n",
    "                if x.right:\n",
    "                    qu.append(x.right)\n",
    "                ans += x.val\n",
    "                del qu[0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0,0\n",
    "            if not root.left and not root.right:\n",
    "                return 1,root.val\n",
    "            ld,ls = dfs(root.left)\n",
    "            rd,rs = dfs(root.right)\n",
    "            if ld == rd:\n",
    "                return ld + 1,ls + rs\n",
    "            if ld < rd:\n",
    "                return rd + 1,rs\n",
    "            return ld + 1,ls\n",
    "        \n",
    "        return dfs(root)[1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
